1. Field of the Invention
The present invention generally relates to a method to allow a receiver of a message to verify the message integrity (i.e., that the received message is identical, with high probability, to the message at the time of sending) and, more particularly, to a method that protects the integrity of messages that are encrypted by stream ciphers, and protects them against changes by a malicious attacker. The invention also serves to detect when synchronization is lost between the sender and receiver, thus enabling resynchronization.
2. Description of the Prior Art
Authentication is a process which proves that someone or something is valid or genuine. In a computer system or communications network, authentication is an important part of data security. All authentication schemes check the validity of one or more parameters. For example, authentication of a person's identity requires a test in which a secret or nonforgeable parameter is supplied by that person with a claimed identity (ID). By checking the validity of the supplied parameter (ID), the system can decide whether the person is who he claims to be.
Message authentication is a process that allows the receiver of a message to verify its integrity; i.e., to verify the fact that the received message is identical (with high probability) to the message at the time of sending. Cyclic redundancy codes (CRCs) are widely used for error detection in communication networks. Such codes are generated by a polynomial division. However, message authentication using CRCs is usually performed on transmitted data with no connection to security, but just as means to detect involuntary alteration. For security purposes, a mechanism is required to prevent a malicious intruder from modifying the message contents, including the originator and destination address, without the alteration being detected. Standard mechanisms, such as CRC, are not capable of dealing with malicious intervention since they are fixed and known procedures, and thus allow any intruder to authenticate any message of its choice.
M. O. Rabin in "Figerprinting by Random Polynomials", Tech. Rep. TR-15-81, Center for Research in Computing Technology, Harvard Univ., Cambridge, Mass. (1981), proposed a fingerprint function which, like CRCs, uses a polynomial division as its basic authentication operation. In the Rabin method, the check-sum is not transmitted and is therefore not available to authenticate the message.
Cryptography offers a highly secure means to authenticate transmitted messages. However, while some message encryption methods may provide some integrity check as a by-product, the common encryption method of Additive Stream Cipher cryptosystems does not help the task of message authentication at all. Thus, the need for a message authentication mechanism is even greater then when using other encryption methods. In fact, when using these methods of encryption, it is very easy to modify a message even after encryption. Indeed, if C is the ciphertext corresponding to the message M (that is, C=E(M), where E is the encryption function), then C.sym.M' is the ciphertext corresponding to M.sym.M', since C.sym.M'=E(M.sym.M'). Here the symbol ".sym." denotes a bitwise Exclusive OR operation. Therefore, by intercepting an encrypted message M, one can easily modify its contents to M.sym.M' without being noticed by the decryption algorithm. A secure message authentication method should detect any tampering of the encrypted data, with high probability.
In addition, the authentication process (which is performed on the plain data, i.e., before encryption and after decryption) serves as a certificate of correct decryption, a feature which is essential to verify encryption/decryption synchronization between sender and receiver in stream cipher systems. In such systems, the sender and receiver need to synchronize the changes in their states; otherwise, a correct decryption is not possible. In addition, the authentication method must be very fast in order to support high data transmission rates.